Termination w.r.t. Q proof of TRS/SK904.43.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

F(g(h(x, y))) → F(h(s(x), y))
+¹(x, s(y)) → +¹(x, y)
F(h(x, h(y, z))) → +¹(x, y)
F(h(x, h(y, z))) → F(h(+(x, y), z))
F(g(f(x))) → F(h(s(0), x))
+¹(s(x), y) → +¹(x, y)
+¹(x, +(y, z)) → +¹(x, y)
+¹(x, +(y, z)) → +¹(+(x, y), z)

The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

F(g(h(x, y))) → F(h(s(x), y))
+¹(x, s(y)) → +¹(x, y)
F(h(x, h(y, z))) → +¹(x, y)
F(h(x, h(y, z))) → F(h(+(x, y), z))
F(g(f(x))) → F(h(s(0), x))
+¹(s(x), y) → +¹(x, y)
+¹(x, +(y, z)) → +¹(x, y)
+¹(x, +(y, z)) → +¹(+(x, y), z)

The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

+¹(x, s(y)) → +¹(x, y)
F(g(h(x, y))) → F(h(s(x), y))
F(h(x, h(y, z))) → +¹(x, y)
F(h(x, h(y, z))) → F(h(+(x, y), z))
+¹(s(x), y) → +¹(x, y)
F(g(f(x))) → F(h(s(0), x))
+¹(x, +(y, z)) → +¹(x, y)
+¹(x, +(y, z)) → +¹(+(x, y), z)

The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 2 SCCs with 3 less nodes.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ QDPOrderProof

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

+¹(x, s(y)) → +¹(x, y)
+¹(s(x), y) → +¹(x, y)
+¹(x, +(y, z)) → +¹(x, y)
+¹(x, +(y, z)) → +¹(+(x, y), z)

The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

+¹(x, s(y)) → +¹(x, y)
+¹(x, +(y, z)) → +¹(x, y)
+¹(x, +(y, z)) → +¹(+(x, y), z)

The remaining pairs can at least be oriented weakly.

+¹(s(x), y) → +¹(x, y)

Used ordering: Combined order from the following AFS and order.
+¹(x1, x2) = +¹(x2)
s(x1) = s(x1)
+(x1, x2) = +(x1, x2)
0 = 0

Recursive Path Order [2].
Precedence:

+₂ > s₁ > +^1₁
0 > +^1₁

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ QDPOrderProof

              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

+¹(s(x), y) → +¹(x, y)

The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

+¹(s(x), y) → +¹(x, y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
+¹(x1, x2) = x1
s(x1) = s(x1)

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ PisEmptyProof

              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

F(h(x, h(y, z))) → F(h(+(x, y), z))

The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

F(h(x, h(y, z))) → F(h(+(x, y), z))

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
F(x1) = F(x1)
h(x1, x2) = h(x2)
+(x1, x2) = x1
0 = 0
s(x1) = s

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ EdgeDeletionProof

        ↳ QDP

          ↳ DependencyGraphProof

            ↳ AND

              ↳ QDP

              ↳ QDP

                ↳ QDPOrderProof

                  ↳ QDP

                    ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(0, y) → y
+(s(x), y) → s(+(x, y))
+(x, +(y, z)) → +(+(x, y), z)
f(g(f(x))) → f(h(s(0), x))
f(g(h(x, y))) → f(h(s(x), y))
f(h(x, h(y, z))) → f(h(+(x, y), z))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.